package com.jojo.intermediate.day13_linkedList;

import com.jojo.elementary.entity.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 143、重排链表
 *
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 *
 * 示例 2：
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 *
 */
public class ResetLinkedList {

    /** myCode 双指针（从中间截取链表翻转） 时间：O(n)  空间：O(1) */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null){
            return;
        }
        int length = 0;
        int a = 1;
        ListNode count = head;
        ListNode middle = head;
        //判断链表长度
        while (count != null){
            length++;
            count = count.next;
        }
        //找出中间节点
        while (a < length / 2){
            a++;
            middle = middle.next;
        }
        ListNode temp = middle;
        middle = middle.next;
        temp.next = null;
        //翻转后面的链表
        middle = reverseList(middle);
        //交换节点
        ListNode cur = head;
        while (cur != null && middle != null){
            ListNode hNext = cur.next;
            ListNode mNext = middle.next;
            cur.next = middle;
            if (hNext != null){
                middle.next = hNext;
            }
            cur = hNext;
            middle = mNext;
        }
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /** pe.线性表  时间：O(n)  空间：O(n) */
    public void reorderLis2t(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,7,3,4,5,6};
        ListNode head = new ListNode(arr[0]);
        ListNode cur = head;
        for (int i = 1;i < arr.length;i++){
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
        ResetLinkedList reset = new ResetLinkedList();
        reset.reorderList(head);
        while (head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }
}
